
class Solution {
   public TreeNode buildTree(int[] inorder, int[] postorder) {
      // inorderMap = new HashMap();
       for (int i = 0; i< inorder.length; i++) {
           inorderMap.put(inorder[i],i);
       }  
       int n = postorder.length - 1;
       //System.out.println(rootIndex);
       //System.out.println("len="+len);
       return dfs (inorder, 0, n, postorder, 0, n);
       //return null;
   }

   private TreeNode dfs(int[] inorder, int inFrom, int inTo, int[] postorder, int poFrom, int poTo) {
       if (inTo - inFrom < 0 ) return null; // sub tree length <=0 exit
       // get the root index from the last element of postorder
       // build the new sub-tree via root
       //int rootVal = postorder[postorder.length-1];
       int rootVal = postorder[poTo];
       TreeNode root = new TreeNode(rootVal);
       //int k = inorderMap.get(postorder[postorder.length-1]);  // root index in inorder
       int k = inorderMap.get(rootVal);  // root index in inorder
       System.out.println("k is " + k);
       // Left sub tree
       // k is the index of root in inorder
       // inorder : inFrom to k -1
       // postorder: poFrom to length of left sub-tree -1.     
       // the length of left sub tree is the same no matter inorder or postorder
       // length of left sub tree = ((k - 1) - inFrom) + 1 = k - inFrom
       // Thus postorder poTo = poFrom + length of left sub tree - 1 
       // = poFrom + (k - inFrom) -1
       root.left = dfs(inorder, inFrom, k-1, postorder, poFrom, poFrom + (k - inFrom) -1);
       
       
       // Right sub tree
       // k is the index of root in inorder
       // inorder: k + 1 to inTo
       // postorder: end of left sub tree + 1 to  poTo  - 1
       // the length of right sub tree is the same, no matter inorder or postorder
       // length of right sub tree is (inTo - (k+1)) +1
       // postorder: poFrom + (inTo - (k+1)) + 1   to  poTo -1
       //root.right = dfs(inorder, k+1, inTo, postorder, poFrom + (inTo-(k+1) +1), poTo-1);
       root.right = dfs(inorder, k+1, inTo, postorder, k-inFrom + poFrom, poTo-1);
       
       return root;
   }
   HashMap<Integer, Integer> inorderMap = new HashMap<>();
}

